第63章 倍增法

倍增法(Binary Lifting)是一种基于"成倍增长"思想的高效算法，通过预处理将问题分解为多个$2$的次规模的子问题，从而在查询时实现快速合并求解。该算法在时间复杂度上通常能将线性查询优化为对数级，广泛应用于数论、图论、字符串处理等领域。

63.1 倍增法的基本原理

63.1.1 核心思想

倍增法的核心是预处理出规模为$2^{0},2^{1},2^{2},...,2^{k}$的子问题的解，在查询时将原问题分解为若干个2的幂次对应的子问题，通过组合子问题的解得到原问题的答案。其本质是利用二进制表示的特性，将任意整数表示为若干个不重复的2的幂次之和，从而实现高效的分解与合并。

63.1.2 预处理与查询流程

预处理阶段：

1. 确定需要预处理的最大幂次$k$（$k$为满足$2^{k} ≤n$的最大整数，即$k=\log_{2} n$）。
2. 对于每个位置$i$，预处理出以$i$为起点、长度为$2^{j}$区间的信息，记为$f[i][j]$。
3. 预处理递推关系：

$$f[i][j] = combine(f[i][j-1],\ f[i+2^{j-1}][j-1])$$

其中$combine$为合并两个子问题解的函数。

查询阶段：

1. 将查询规模$m$拆解为二进制：$m=2^{a}+2^{b}+\dots+2^{c}$
2. 依次处理每一个2的幂次子区间，通过$combine$函数合并结果得到最终答案。

63.1.3 时间复杂度

• 预处理：$O(n \log n)$
• 单次查询：$O(\log n)$

63.2 倍增法的典型应用：快速幂

快速幂是倍增法在数论中的经典应用，用于高效计算$a^{n} \bmod m$，避免朴素循环$O(n)$的时间开销。

原理： 将指数$n$拆分为二进制，例如$n=5$二进制为$101$，等价$2^{2}+2^{0}$，则$a^{5}=a^{4} × a^{1}$。 提前递推$a^{2^{0}},a^{2^{1}},a^{2^{2}}...$，遍历二进制位，若当前位为1则累乘对应幂次，全程取模防止溢出。

实现代码

long long fastPower (long long a, long long n, long long m) {
    long long result=1;
    a %= m;
    while (n>0){
        if(n & 1){
            result = (result * a) % m;
        }
        a = (a * a) % m;
        n >>= 1;
    }
    return result;
}